package com.neteasy.interview;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe:
 * @date 2021/07/04
 */

public class One_WarehouseDistribution_Floyd {

    public int floyd(int[][] graph , int N , int src){
        for(int k = 1 ; k <= N ; k ++){
            for(int i = 1 ; i <= N ; i ++){
                for(int j = 1 ; j <= N ; j ++){
                    if(graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE){
                        graph[i][j] = Math.min(graph[i][j] , graph[i][k] + graph[k][j]);
                    }
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for(int i = 1 ; i <= N ;i ++){
            ans = Math.max(graph[src][i] , ans);
        }
        if(ans == Integer.MAX_VALUE) return -1;
        return ans;
    }


    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt(); int K = input.nextInt(); int M = input.nextInt();
        int[][] graph = new int[N + 1][N + 1];
        for(int i = 0 ; i <= N ; i ++){
            Arrays.fill(graph[i], Integer.MAX_VALUE);
            graph[i][i] = 0;
        }
        for(int i = 0 ; i < M ; i ++){
            int v = input.nextInt(); int u = input.nextInt(); int w = input.nextInt();
            graph[v][u] = w;
        }
        One_WarehouseDistribution_Floyd floyd = new One_WarehouseDistribution_Floyd();
        System.out.println(floyd.floyd(graph , N , K));
    }
}
/*
6 2 5
2 1 1
2 6 2
1 3 3
3 4 1
6 5 2
* */
